package com.dataStructure.堆;

import java.util.Comparator;

@SuppressWarnings("all")
//最大堆
public class BinaryHeap<E> extends AbstractHeap<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private E[] elements;

    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);

        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap() {
        this(null, null);
    }

    @Override
    public void clear() {
        size = 0;
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapaity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();

        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        size--;

        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }

        return root;
    }

    private void heapify() {
        // 自上而下的上滤
//		for (int i = 1; i < size; i++) {
//			siftUp(i);
//		}

        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    public static void main(String[] args) {
        System.out.println(3 >> 1);
    }

    /**
     * 让索引位置的元素下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        //非叶子节点数量
        int half = size >> 1;

        //第一个叶子节点的索引 == 非叶子节点的数量
        //必须保证index位置是叶子节点
        while (index < half) {
            //index的节点有两种情况
            //1. 只有左子节点
            //2. 同时有左右节点

            //找出左右节点较大的那一个
            //默认先拿左子节点的索引
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            //右子节点
            int rightIndex = childIndex + 1;

            //选出左右节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }

            if (compare(element, child) >= 0) break;

            //将子节点放到存放index位置
            elements[index] = child;
            //重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

    /**
     * 让索引位置的元素上虑
     *
     * @param index
     */
    private void siftUp(int index) {
        E e = elements[index];
//        while (index > 0) {
//            //获取父节点索引
//            int pindex = (index - 1) >> 1;
//            E p = elements[pindex];
//            if (compare(e, p) <= 0) return;
//
//            //交换index,pindex位置的内容
//            E tmp = elements[index];
//            elements[index] = elements[pindex];
//            elements[pindex] = tmp;
//
//            //重新赋值index
//            index = pindex;
//        }
        //优化代码
        while (index > 0) {
            //获取父节点索引
            int pindex = (index - 1) >> 1;
            E p = elements[pindex];
            if (compare(e, p) <= 0) break;

            //将元素存储在index的位置
            elements[index] = p;

            //重新赋值index
            index = pindex;
        }
        elements[index] = e;
    }

    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is Empty");
        }
    }

    //扩容
    private void ensureCapaity(int capaity) {
        int oldCapaity = elements.length;
        if (oldCapaity >= capaity) return;
        //扩容为原数组的1.5倍
        int newCapaity = oldCapaity + (oldCapaity >> 1);
        E[] newElements = (E[]) new java.lang.Object[newCapaity];
        for (int i = 0; i < size - 1; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println("beforekuorong:" + oldCapaity + "afterkuorong" + newCapaity);
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element not be null");
        }
    }
}
